The present invention relates to spread-spectrum communications, in general, and to calculations of masks for generation of shifted pseudo-noise (PN) sequences, in particular.
In direct sequence spread-spectrum communications, a pseudo-noise (PN) sequence is used for spreading an information signal. The PN sequence, is typically a long binary sequence. In the IS-95 standard, for example, the length of the PN sequence is 215. In the wideband code division multiple access (W-CDMA) standard, the lengths are 218 and 242.
One technique for generating PN sequences is through the use of a maximum length shift register, as shown in FIG. 1, to which reference is now made. A linear feedback shift register 100 having R bits is connected in a feedback loop to a XOR unit 102. Initially, shift register 100 contains an R-bit integer. A single bit B is output from shift register 100 with every tick of a clock (not shown), The output bit B may be, for example, the least significant bit of shift register 100, or may be a more complex combination of the bits of shift register 100. XOR unit 102 is connected to particular bits of shift register 100 in a feedback loop.
In the example shown in FIG. 1, for each tick of the clock: a) XOR unit 102 performs a XOR operation an the contents of bit 2, bit 3 and bit (Rxe2x88x921) of shift register 100, b) shift register 100 is shifted to the right by one bit, outputting as output bit B the contents of bit 1, and c) the result of the XOR operation is stared in bit R of shift register 100. The procedure is repeated for each tick of the clock, thereby producing a sequence X of output bits B.
The R-bit integer stored in shift register 100 at any given time is known as the xe2x80x9cstatexe2x80x9d of shift register 100. Clearly there are 2R possible states of shift register 100. As the clock marks 2Rxe2x88x921 ticks, shift register 100 cycles through 2Rxe2x88x921 possible states (excluding the zero state). The resultant sequence X of output bits B , with a zero added, has a periodicity of 2R, is said to have a length of 2R, and is known as a maximal length linear binary sequence. For some feedback arrangements, however, the sequence is not a maximal length sequence. Rather, for these arrangements, shift register 100 cycles through only some of the 2Rxe2x88x921 possible states, resulting in a sequence X of output bits B having a periodicity of less than 2R.
The sequence X satisfies a polynomial, for example h(X)=X18+X7+1=0, where X0xe2x89xa11 is the unshifted sequence X, X7 is the sequence X shifted by a delay of 7, X18 is the sequence X shifted by a delay of 18, and the summation is a XOR-operation. What the polynomial represents is the fact that if the sequence X and its shifted versions for delays of 7 and 18 are XOR added, the result is a sequence of all zero bits. The polynomial h(X) is chosen so that the sequence X is noisy. However, since the sequence X is periodic and not truly noisy, the sequence is called a pseudo-noise (PN) sequence.
In direct sequence spread-spectrum communications, it is frequently necessary to calculate in real-time a shifted version of the PN sequence, where the shift, also known as the xe2x80x9cdelayxe2x80x9d, is unknown prior to real-time and may be of the order of the size of 2R. As is known in the art, calculation of a shifted version of a PN sequence is accomplished in hardware using a mask. FIG. 2, to which reference is now made, is a schematic illustration of a prior art hardware system for calculating an arbitrary shifted version of a PN sequence. As in FIG. 7 , shift register 200 has R bits and is connected to a XOR unit 202 in a feedback loop. The R bits of shift register 200 are connected via R switches 204 to a XOR unit 206. A mask M(d) for a delay d indicates which of the switches 204 are closed and which are open. XOR unit 206 sums the contents of the bits whose switches 204 are closed and produces an output bit Bxe2x80x2. For each tick of the clock, the contents of shift register 900 change according to the feedback loop, and the resulting output bit Bxe2x80x2 produced by XOR unit 206 reflects this change. If the PN sequence comprising the output bits B is denoted S[n], the shifted PN sequence comprising the output bits Bxe2x80x2 is denoted S[nxe2x88x92d].
Mask M(d) can be represented as a binary vector of length R, [cR-1(d) cR-2(d). . . ci(d) c0(d)], where c1(d) has a value of 1 when the ith switch should be closed and a value of 0 when the ith switch should be open.
Mask M(d) can also be represented as a polynomial. For example, the polynomial X12+X5+X0 indicates that the switches for bits 12, 5 and 0 of shift register 100 are closed, and all the other switches are open. In general, for an arbitrary delay d ,the mask M(d) that determines which of the switches to close and which to open in order to calculate the PN sequence that is shifted by the delay d is given by:             M      ⁢              (        d        )              =                  ∑                  i          =          0                          R          -          1                    ⁢                                    c            i                    ⁢                      (            d            )                          ⁢                  X          xe2x80x2                      ,
where i is an index for the R switches and the R bits of the shift register, and c, (d) is as defined hereinabove, and Xxe2x80x2 denotes the sequence X ,shifted by a delay of i.
The task of calculating an arbitrary shifted version of a PN sequence is therefore equivalent to the task of mask calculation. The goal is to find a method for calculating the mask for an arbitrary delay, even a large delay, quickly and with minimum use of valuable memory and power resources.
The most trivial solution would be to calculate in advance the mask for every one of the possible 2R delays, and to store the resulting 2R R-bit integers in memory. Then during online operation, when the arbitrary delay becomes known, the appropriate R-bit mask is read from the memory. Since R typically has a value of 15 or 18, this solution is impractical due to its requirement of a huge dedicated memory.
The articles xe2x80x9cGeneration of delayed replicas of maximal-length linear binary sequencesxe2x80x9d, S. H. Tsao, Proc. Inst. Elec. Engrs. (London) 111, No. 11, November 1964, pp. 1803-1807, and xe2x80x9cDiscussion on generation of delayed replicas of maximal length binary sequencesxe2x80x9d, P. D. Roberts, A. C. Davies and S. H. Tsao. Proc. Inst. Elec. Engrs. (London) 112, No. 4, April 1965, pp. 702-704, are among the earliest to deal with delays in shift registers. However, the methods described therein are not appropriate for handling large delays.
Algorithms that are capable of handling large delays are either matrix fast multiplication methods or polynomial fast division methods. For sparse matrices or sparse polynomials other methods based on this sparseness may be used in particular, the article xe2x80x9cA simple technique for the determination of delayed maximal length binary sequencesxe2x80x9d, A. Miller, A. Brown and P. Mars, IEEE Trans. Computers C-26, No. 8, August 1977, pp. 808-811, describes a tree-like structure representation for trinomials, but this algorithm does not outperform fast polynomial division.
Matrix multiplication algorithms are based on the state machine representation of the shift register, as described in R. L. Peterson, R. E. Ziemer and D. E. Borth, Introduction to Spread Spectrum Communications, Prentice Hall, New Jersey (1995) and in xe2x80x9cM-sequences: what they are and how they can be implementedxe2x80x9d, The April Spread Spectrum Sourcebook, Appendix A, Publication No. 121 of the Radio Amateur""s Library, The American Radio Relay League, USA. The multiplication process may be optimized by the so-called logarithmic (usually loge) route corresponding to the binary representation of the delay d , This is described in xe2x80x9cMatrix method to determine shift-register connections for delayed pseudo-random binary sequencesxe2x80x9d, B. Ireland and J. Marshall, Electron. Letters, 4, No. 21, 1968, pp. 467-468 and in xe2x80x9cM-sequences: what they are and how they can be implementedxe2x80x9d, The April Spread Spectrum Sourcebook, Appendix A. Such algorithms have a number of operations NOP on the order of R2log2d.
Currently, the polynomial approach is the source of the best known algorithms. All such algorithms are based on the Davies theorem, described in xe2x80x9cDelayed versions of maximal-length linear binary sequencesxe2x80x9d, A. Davies, Electron. Letters. 1, No. 3, May 1965, pp. 61-62, that for a delay d, the corresponding mask M(d) is calculated as Xdmodh(X) where h(X) is the shift register polynomial of order R. The articles xe2x80x9cShift register connections for delayed versions of m-sequencesxe2x80x9d, A. N. Van Luyn. Electron. Letters.14, No. 22, October 1978, pp. 713-715, and xe2x80x9cA simple method for determination of feedback shift register connections for delayed maximal-length sequencesxe2x80x9d, K. P. Yiu. Proc. IEEE 68 No. 4, April 1980, pp. 537-538, propose fast realizations of this long division based on different log2 routes. Such algorithms have a number of operations NOP, on the order of Rlog2d.
European Patent Application EP0901236 to Matsushita Electric Industrial Co., Ltd., published Mar. 10, 1999, describes a PN code generator using polynomial division and look-up tables. According to this method, only equidistant masks are used. The usual long-polynomial division further calculates a fine mask.